home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 11 - 1995 / 11.01 Jan 95 / ProgChalHuffman.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-14  |  16.5 KB  |  536 lines  |  [TEXT/KAHL]
  1. /*
  2.  *  HuffmanDecode
  3.  *  Copyright (c) 1994  J Robert Boonstra
  4.  *
  5.  * Problem Statement:
  6.  *
  7.  * Given a symbol table, decompress the Huffman encoded 
  8.  * input stream and return the number of decompressed
  9.  * bytes.
  10.  *
  11.  * Solution Strategy
  12.  *
  13.  * Use the untimed initialization routine to create a tree
  14.  * structure corresponding to the sym values in the symbol
  15.  * table.  In the timed decode routine, traverse the tree.
  16.  * When a leaf node is encountered, output the corresponding
  17.  * value, and begin traversing the tree again from the root.
  18.  *
  19.  * We determine whether there is enough storage for the 
  20.  * tree structure by trying to construct it.  If there is
  21.  * not enough storage, set up a simple table of pointers
  22.  * into the symbol table based on symbol length.  This is
  23.  * not especially efficient, but it produce correct results. 
  24.  */
  25.  
  26. #pragma options(honor_register,!assign_registers)
  27.  
  28. /*
  29.  * TYPEDEFS and DEFINES
  30.  */ 
  31. #define ulong  unsigned long
  32. #define ushort unsigned short
  33. #define uchar  unsigned char
  34.  
  35. /*
  36.  * SymElem is the data structure provided in the problem
  37.  * definition.  Symbols are sorted by symLength and within
  38.  * length by sym.
  39.  */
  40. typedef struct SymElem {
  41.   unsigned short symLength;
  42.   unsigned short sym;
  43.   unsigned short value;
  44. } SymElem, *SymElemPtr;
  45.  
  46. /*
  47.  * DecodeNode is a node in the tree used to decode the 
  48.  * input stream.  The zeroP and oneP values are offsets
  49.  * into the tree corresponding to reading a 0 or a 1 given
  50.  * the prior input.  Note that the zeroP field is used at a
  51.  * leaf node (identified by a zero in the oneP field) to 
  52.  * represent the SymElem value.  The offsets are stored
  53.  * relative to the current tree position for efficiency
  54.  * in calculating the address.  Note also that 16 bits are 
  55.  * enough to access the max available 256K (64K nodes of 
  56.  * 4 bytes each).  In cases where only 64K storage is used,
  57.  * the offsets are premultiplied by sizeof(DecodeNode) to
  58.  * squeeze out a little additional efficiency at some small
  59.  * expense in code size.
  60.  */
  61. typedef struct DecodeNode {   
  62.     ushort zeroP;   /* index of right tree node, or value */ 
  63.     ushort oneP;    /* index of left tree node            */ 
  64. } DecodeNode; 
  65.  
  66. typedef struct SymDecode {
  67.         SymElemPtr symP;
  68.         ushort numEntries;
  69.         ushort align;
  70. } SymDecode;
  71. /*
  72.  * PROTOTYPES
  73.  */
  74. void *HuffmanDecodeInit(SymElemPtr theSymTable,
  75.   unsigned short numSymElems,
  76.   unsigned long maxMemoryUsage);
  77.  
  78. unsigned long HuffmanDecode(SymElemPtr theSymTable,
  79.   unsigned short numSymElems, char *bitsPtr,
  80.   unsigned long numBits, unsigned short *outputPtr,
  81.   void * privateHuffDataPtr);
  82.  
  83. #define kUnused (ushort)0xFFFF
  84. #define kTerminalNode 0
  85. #define InitializeNewNode()                                \
  86. {                                                          \
  87.     if ((void *)pFree > (void *)pMax)                      \
  88.       goto notEnoughStorage;                               \
  89.     pFree->oneP = kUnused;                                 \
  90.     pFree->zeroP = kUnused;                                \
  91. }
  92.  
  93. #define kGMode 0
  94. #define kSEP 4
  95. #define kGlobalStorageSize (kSEP+16*sizeof(SymDecode))
  96.  
  97. #define gMode *(short *)((char *)privateHuffDataPtr+kGMode)
  98.  
  99. void *HuffmanDecodeInit(SymElemPtr theSymTable,
  100.   unsigned short numSymElems,
  101.   unsigned long maxMemoryUsage)
  102. {
  103. register DecodeNode *p;
  104. register DecodeNode *pOrig;
  105. register DecodeNode *pFree;
  106. register ulong pMax;
  107. register ushort i;
  108. register ulong nodeNum=1;
  109. SymDecode *theSymElemPtr;
  110. SymElemPtr sP;
  111. void *privateHuffDataPtr;
  112. ulong count;
  113. ushort sym,maxLng,maxDiff=0;
  114. /*
  115.  * Allocate entire memory allocation, return if allocation
  116.  * fails.
  117.  */
  118.   if (0 == (p=privateHuffDataPtr = NewPtr(maxMemoryUsage)))
  119.      return 0;
  120.   gMode = 0;
  121. /* 
  122.  * Initialize SymElem pointers
  123.  */
  124.   theSymElemPtr = (SymDecode *)((char *)privateHuffDataPtr +
  125.                                                       kSEP);
  126.   sP = theSymTable;
  127.   count = 0;
  128.   sym = theSymTable->sym;
  129.   for (i=1; i<=16; ++i) {
  130.     ushort oldCount;
  131.     oldCount = count;
  132.     theSymElemPtr->symP = sP;
  133.     while ((sP->symLength==i) && (count<numSymElems))
  134.       { ++count;  ++sP; }
  135.     theSymElemPtr++->numEntries = count-oldCount;
  136.   }
  137. /*
  138.  * Initialize tree pointers.
  139.  */
  140.   p = (DecodeNode *)(kGlobalStorageSize + 
  141.                                 (char *)privateHuffDataPtr);
  142.   pOrig = pFree = p;
  143.   pMax = (ulong)((char *)p + maxMemoryUsage -
  144.                 (kGlobalStorageSize + sizeof(DecodeNode)) );
  145. /*
  146.  * Initialize root of tree.
  147.  */
  148.   InitializeNewNode();
  149.   ++pFree;
  150. /*
  151.  * Loop over symbol table elements.
  152.  * Insert each symbol into the tree.
  153.  * Tree is traversed by following the zeroP/oneP indices 
  154.  * corresponding to the bits of the sym field in the symbol
  155.  * table, from most significant to least significant bit.
  156.  * Leaves of the tree are indicated by oneP==kTerminalNode.
  157.  * The zeroP field of leaf nodes contains the decompressed 
  158.  * output for the bit sequence that led to the leaf when 
  159.  * the oneP field is kTerminalNode.
  160.  */
  161.   for (i=0; i<numSymElems; ++i) {
  162.     SymElemPtr sP;
  163.     register short sym;
  164.     ushort value;
  165.     register ushort symLength;
  166.     sP = theSymTable+i;
  167.     sym = sP->sym;
  168.     value = sP->value;
  169.     symLength = sP->symLength;
  170.     p = pOrig;
  171. /*
  172.  * Loop over bits in the sym field.
  173.  */
  174.     sym <<= (16-symLength);
  175.     do {
  176.       if (0 > sym ) {
  177. /*
  178.  * Process a 1, allocate a new node if one is needed.
  179.  */
  180.         if (kUnused == p->oneP) { 
  181.           InitializeNewNode();
  182.           p->oneP = (pFree-p);
  183.           if (p->oneP > maxDiff) maxDiff = p->oneP;
  184.           p = pFree++;
  185.         } else {
  186.           p += p->oneP;
  187.         }
  188.       } else {
  189. /*
  190.  * Process a 0, allocate a new node if one is needed.
  191.  * Note that since we reuse the zeroP field later to contain
  192.  * the value to be output, this code depends on having a
  193.  * correct (i.e. deterministic) Huffman encoding in
  194.  * theSymTable, and will crash spectacularly otherwise.
  195.  */
  196.         if (kUnused == p->zeroP) {
  197.           InitializeNewNode();
  198.           p->zeroP = (pFree-p);
  199.           if (p->zeroP > maxDiff) maxDiff = p->zeroP;
  200.           p = pFree++;
  201.         } else {
  202.           p += p->zeroP;
  203.         }
  204.       }
  205.       sym <<= 1;
  206.     } while (--symLength);
  207. /*
  208.  * Insert value into leaf node.
  209.  */
  210.     p->zeroP = value;
  211.     p->oneP = kTerminalNode;
  212.     maxLng = sP->symLength;
  213.   }
  214. /* 
  215.  * Premultiply offsets by node size for "fast" mode.
  216.  */
  217.   if ( (1<<14)-1 > maxDiff  ) {
  218.     gMode = 1;
  219.     p = pFree;
  220.     do {
  221.       --p;
  222.       if (p->oneP != kTerminalNode) {
  223.         if (p->zeroP != kUnused)
  224.           p->zeroP *= sizeof(DecodeNode);
  225.         if (p->oneP != kUnused)
  226.           p->oneP *= sizeof(DecodeNode);
  227.       }
  228.     } while (p>pOrig);
  229.   }
  230.   goto done;
  231. notEnoughStorage: 
  232. /*
  233.  * If we do not have enough storage for the tree, fall back
  234.  * on a slower technique requiring less storage.
  235.  */
  236.   gMode = 2;
  237. done:
  238.   return privateHuffDataPtr;
  239. }
  240.  
  241. #define ProcessBit(mask,bitNum)                            \
  242. { register ulong temp;                                     \
  243.   if (!(theChar & mask)) temp = tP->zeroP;                 \
  244.   else                   temp = oneP;                      \
  245.   temp *= sizeof(DecodeNode);                              \
  246.   t += temp;                                               \
  247.   if (kTerminalNode == (oneP = tP->oneP))  {               \
  248.     *outP++ =  tP->zeroP;                                  \
  249.     t = (char *)decode_tree;                               \
  250.     oneP = tP->oneP;                                       \
  251.   }                                                        \
  252. }
  253.  
  254. #define ProcessBitFast(mask,bitNum)                        \
  255. { register ulong temp;                                     \
  256.   if (!(theChar & mask)) temp = tP->zeroP;                 \
  257.   else                   temp = oneP;                      \
  258.   t += temp;                                               \
  259.   if (kTerminalNode == (oneP = tP->oneP))  {               \
  260.     *outP++ =  tP->zeroP;                                  \
  261.     t = (char *)decode_tree;                               \
  262.     oneP = tP->oneP;                                       \
  263.   }                                                        \
  264. }
  265.  
  266. #define ProcessBitSlow(mask,bitNum,keepMask,next)          \
  267. { register ushort temp;                                    \
  268.   if (!(theChar & mask)) temp = tP->zeroP;                 \
  269.   else                   temp = oneP;                      \
  270.   if (temp != kUnused) {                                   \
  271.     temp *= sizeof(DecodeNode);                            \
  272.     t += temp;                                             \
  273.     if (kTerminalNode == (oneP = tP->oneP))  {             \
  274.       *outP++ =  tP->zeroP;                                \
  275.       t = (char *)decode_tree;                             \
  276.       oneP = tP->oneP;                                     \
  277.       theSym=0;  theSymLng=0;                              \
  278.       theChar &= keepMask;                                 \
  279.       bitStart = bitNum-1;                                 \
  280.       next;                                                \
  281.     }                                                      \
  282.   } else {                                                 \
  283.     theBitNum = bitNum;                                    \
  284.     goto overflow;                                         \
  285.   }                                                        \
  286. }
  287.  
  288. unsigned long HuffmanDecode(SymElemPtr theSymTable,
  289.   unsigned short numSymElems, char *bitsPtr,
  290.   unsigned long numBits, unsigned short *outputPtr,
  291.   void * privateHuffDataPtr)
  292. {
  293. register char *bitsP = bitsPtr;
  294. register ushort *outP = outputPtr;
  295. register char *t = (char *)privateHuffDataPtr + 
  296.                                          kGlobalStorageSize;
  297. #define tP ((DecodeNode *)t)
  298.  
  299. register uchar theChar; 
  300. register ushort oneP;
  301. register ulong count; 
  302. ushort state;
  303.  
  304.   oneP = ((DecodeNode *)t)[0].oneP;
  305.   state = 0;
  306. /*
  307.  * Set up loop count to loop over complete input bytes, and
  308.  * jump past the switch statement into the loop.
  309.  * The billKarsh-inspired switch--do subterfuge allows us  
  310.  * to optimize the main loop and still reuse code for the 
  311.  * leftover bits at the end.
  312.  */
  313.   count = numBits>>3;
  314. /*
  315.  * Select case.
  316.  */
  317.   {
  318.     register ushort mode;
  319.     if (0 == (mode = *(ushort *)(t - kGlobalStorageSize)) )
  320.       goto start;
  321.     if (1 == mode) goto startFast;
  322.     goto slowest;
  323.   }
  324. /*
  325.  * CASE 0
  326.  *
  327.  * This section processes the case where the decode tree
  328.  * fit into available memory, but the offsets are in units
  329.  * of sizeof(long).
  330.  * We jump to doLeftOverBits at the end to pick up the last 
  331.  * byte.
  332.  */
  333. doLeftOverBits:
  334.   state = 1;
  335.   count = 1;                  /* Only one byte to process */
  336.   theChar =  *bitsP;          /* Fetch last byte */
  337.   theChar>>=(8-numBits);      /* Shift bits into position */
  338.   switch (numBits) {
  339.     register ulong decode_tree;
  340. start:
  341.     decode_tree = (ulong)t;
  342.     do { 
  343. bit0:
  344. /*
  345.  * Loop over the bytes in the input stream, decoding as
  346.  * we go.  Rather than loop over the bits in each byte,
  347.  * the bit loop is unrolled for efficiency.
  348.  */
  349.         theChar =  *bitsP++;  /* get input byte */ 
  350. case 0: ProcessBit(0x80,8);     /* process 0th bit */
  351. case 7: ProcessBit(0x40,7);     /* process 1st bit */ 
  352. case 6: ProcessBit(0x20,6);     /* process 2nd bit */ 
  353. case 5: ProcessBit(0x10,5);     /* process 3rd bit */ 
  354. case 4: ProcessBit(0x08,4);     /* process 4th bit */ 
  355. case 3: ProcessBit(0x04,3);     /* process 5th bit */ 
  356. case 2: ProcessBit(0x02,2);     /* process 6th bit */ 
  357. case 1: ProcessBit(0x01,1);     /* process 7th bit */ 
  358.     } while (--count);
  359.   }
  360. /*
  361.  * Make another pass to process the bits in the last byte.
  362.  */
  363.   if (state==0) {
  364.     if (numBits &= 7) goto doLeftOverBits;
  365.   }
  366.   goto done;
  367. /*
  368.  * CASE 1
  369.  *
  370.  * This section processes the case where the decode tree
  371.  * fit into available memory, but the offsets are in units
  372.  * of bytes.
  373.  * We jump to doLeftOverBitsFast at the end to pick up the 
  374.  * last byte.
  375.  */
  376. doLeftOverBitsFast:
  377.   state = 1;
  378.   count = 1;                  /* Only one byte to process */
  379.   theChar =  *bitsP;          /* Fetch last byte */
  380.   theChar>>=(8-numBits);      /* Shift bits into position */
  381.   switch (numBits) {
  382.     register ulong decode_tree;
  383. startFast:
  384.     decode_tree = (ulong)t;
  385.     do { 
  386. bit0Fast:
  387. /*
  388.  * Loop over the bytes in the input stream, decoding as
  389.  * we go.  Rather than loop over the bits in each byte,
  390.  * the bit loop is unrolled for efficiency.
  391.  */
  392.         theChar =  *bitsP++;  /* get input byte */ 
  393. case 0: ProcessBitFast(0x80,8); /* process 0th bit */
  394. case 7: ProcessBitFast(0x40,7); /* process 1st bit */ 
  395. case 6: ProcessBitFast(0x20,6); /* process 2nd bit */ 
  396. case 5: ProcessBitFast(0x10,5); /* process 3rd bit */ 
  397. case 4: ProcessBitFast(0x08,4); /* process 4th bit */ 
  398. case 3: ProcessBitFast(0x04,3); /* process 5th bit */ 
  399. case 2: ProcessBitFast(0x02,2); /* process 6th bit */ 
  400. case 1: ProcessBitFast(0x01,1); /* process 7th bit */ 
  401.     } while (--count);
  402.   }
  403. /*
  404.  * Make another pass to process the bits in the last byte.
  405.  */
  406.   if (state==0) {
  407.     if (numBits &= 7) goto doLeftOverBitsFast;
  408.   }
  409.   goto done;
  410. /* 
  411.  * CASE 2
  412.  *   This code handles the case where the entire decode
  413.  *   tree did not fit into the private storage.  In this
  414.  *   case we use the portion of the tree that did fit, but
  415.  *   we may have to linearly search the SymTable for the
  416.  *   longer symbols.
  417.  */
  418. slowest:
  419. {
  420.   SymDecode *theSymElemPtr;
  421.   SymElemPtr sP;
  422.   short bitStart,theSymLng,theMask,theBitNum,saveCount,x;
  423.   register ushort theSym;
  424.   theSymLng = 0;
  425.   theSym = 0;
  426.   goto startSlow;
  427. doLeftOverBitsSlow:
  428.   state = 1;
  429.   count = 1;                /* Only one byte to process */
  430.   theChar =  *bitsP;        /* Fetch last byte */
  431.   theChar>>=(8-numBits);    /* Shift bits into position */
  432.   switch (numBits) {
  433.     ulong decode_tree;
  434. startSlow:
  435.     decode_tree = (ulong)t;
  436.     do { 
  437.       theChar =  *bitsP++;  /* get input byte */ 
  438.       bitStart = 8;
  439. slow0:                                /* process 0th bit */
  440. case 0: ProcessBitSlow(0x80,8,0x7F,);
  441. slow7:                                /* process 1st bit */
  442. case 7: ProcessBitSlow(0x40,7,0x3F,);
  443. slow6:                                /* process 2nd bit */
  444. case 6: ProcessBitSlow(0x20,6,0x1F,);
  445. slow5:                                /* process 3rd bit */
  446. case 5: ProcessBitSlow(0x10,5,0x0F,); 
  447. slow4:                                /* process 4th bit */
  448. case 4: ProcessBitSlow(0x08,4,0x07,);
  449. slow3:                                /* process 5th bit */
  450. case 3: ProcessBitSlow(0x04,3,0x03,);
  451. slow2:                                /* process 6th bit */
  452. case 2: ProcessBitSlow(0x02,2,0x01,); 
  453. slow1:                                /* process 7th bit */
  454. case 1: ProcessBitSlow(0x01,1,0x00,continue);  
  455.  
  456.       theSym <<= bitStart;
  457.       theSym |= theChar;
  458.       theSymLng += bitStart;
  459.       
  460.       continue; /* continue with next char */
  461. overflow:
  462.       theSym <<= bitStart-theBitNum;
  463.       theSym |= (theChar>>theBitNum);
  464.       theSymLng += bitStart-theBitNum;                                    
  465.       theMask = 1<<(theBitNum-1);
  466.       theChar &= (1<<theBitNum)-1;
  467.       bitStart = theBitNum;
  468.  
  469.       /* search SymTab for theSym */
  470.       saveCount = count;
  471.       theSymElemPtr = (SymDecode *)
  472.                         ((char *)privateHuffDataPtr + kSEP);
  473.       theSymElemPtr += theSymLng-1;
  474. search:
  475.       sP = theSymElemPtr->symP;
  476.       count = theSymElemPtr->numEntries;
  477.       if (count) do {
  478.         if (sP->sym < theSym) goto nextSP;
  479.         if (sP->sym > theSym) goto noSym;
  480.         *outP++ = sP->value;
  481.         if (state != 0) goto done;
  482.         theSymLng = 0;
  483.         theSym = 0;
  484.         theChar &= ((1<<theBitNum)-1);
  485.         bitStart = theBitNum;
  486.         count = saveCount;
  487.         t = (char *)decode_tree;
  488.         oneP = tP->oneP;
  489. next:   switch (theBitNum) {
  490.         case 8:
  491.         case 0:  count = saveCount;
  492.                  goto nextChar0;
  493.         case 1:  goto slow1;
  494.         case 2:  goto slow2;
  495.         case 3:  goto slow3;
  496.         case 4:  goto slow4;
  497.         case 5:  goto slow5;
  498.         case 6:  goto slow6;
  499.         case 7:  goto slow7;
  500. nextSP: ++sP;
  501.         } /* end switch */
  502.       } while (--count);
  503. noSym:if (0 == theBitNum) {
  504.         if (0==--saveCount) {
  505. lastChar:
  506.           if (state!=0) goto done;
  507.           state=1;
  508.           theChar = *bitsP;
  509.           count = 1;
  510.           theBitNum = 8;  theMask = 0x80;
  511.         } else {
  512.           theChar =  *bitsP++;  /* get input byte */ 
  513.           theBitNum = 8;  theMask = 0x80;
  514.         }
  515.       }
  516.       theSym<<=1;
  517.       if (theChar&theMask) theSym|=1;
  518.       --theBitNum;
  519.       theMask>>=1;
  520.       ++theSymElemPtr;
  521.       goto search;
  522. nextChar: 
  523.       theSym <<= 8;
  524.       theSym |= theChar;
  525.       theSymLng += 8;
  526. nextChar0: ;
  527.     } while (--count);
  528.     if ((state==0) && (numBits &= 7)) 
  529.       goto doLeftOverBitsSlow;
  530.   }
  531. }
  532. done: 
  533.     return (char *)outP-(char *)outputPtr;  
  534. }
  535.  
  536.